import sys
from collections import defaultdict
from typing import List


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        window, need = defaultdict(int), defaultdict(int)
        for c in t:
            need[c] += 1
        left, right, valid, start, length = 0, 0, 0, 0, sys.maxsize
        while right < len(s):
            ch = s[right]
            right += 1
            if ch in need.keys():
                window[ch] += 1
                if window[ch] == need[ch]:
                    valid += 1

            while valid == len(need):
                if right - left < length:
                    start = left
                    length = right - left

                leftChar = s[left]
                left += 1

                if leftChar in need.keys():
                    if window[leftChar] == need[leftChar]:
                        valid -= 1
                    window[leftChar] -= 1
        return "" if length == sys.maxsize else s[start:start+length]
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window, need = defaultdict(int), defaultdict(int)
        for c in s1:
            need[c] += 1
        left, right, valid, start, length = 0, 0, 0, 0, sys.maxsize
        while right < len(s2):
            ch = s2[right]
            right += 1
            if ch in need.keys():
                window[ch] += 1
                if window[ch] == need[ch]:
                    valid += 1

            while right - left >= len(s1):
                if valid == len(need):
                    return True

                leftChar = s2[left]
                left += 1

                if leftChar in need.keys():
                    if window[leftChar] == need[leftChar]:
                        valid -= 1
                    window[leftChar] -= 1
        return False

    def findAnagrams(self, s: str, p: str) -> List[int]:
        window, need = defaultdict(int), defaultdict(int)
        for c in p:
            need[c] += 1
        left, right, valid = 0, 0, 0
        res = []
        while right < len(s):
            ch = s[right]
            right += 1
            if ch in need.keys():
                window[ch] += 1
                if window[ch] == need[ch]:
                    valid += 1

            while right - left >= len(p):
                if valid == len(need):
                    res.append(left)

                leftChar = s[left]
                left += 1

                if leftChar in need.keys():
                    if window[leftChar] == need[leftChar]:
                        valid -= 1
                    window[leftChar] -= 1
        return res
